package code.commonAlgorithm;

import java.util.Arrays;

/**
 * @author 26029
 * @date 2025/4/8
 * @description
 */
public class Dijkstra {
    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];         // 距离数组
        boolean[] visited = new boolean[n]; // 标记节点是否访问过

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int i = 0; i < n; i++) {
            int u = -1;
            int minDist = Integer.MAX_VALUE;

            // 找到当前未访问节点中距离最小的
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    u = j;
                }
            }

            // 如果找不到，说明剩下的节点不可达
            if (u == -1) break;

            visited[u] = true;

            // 更新相邻节点的最短距离
            for (int v = 0; v < n; v++) {
                // 未被访问过且有通路
                if (!visited[v] && graph[u][v] != Integer.MAX_VALUE) {
                    if (dist[u] + graph[u][v] < dist[v]) {
                        dist[v] = dist[u] + graph[u][v];
                    }
                }
            }
        }

        // 输出结果
        System.out.println("Vertex\tDistance from Source");
        for (int i = 0; i < n; i++) {
            System.out.println(i + "\t" + (dist[i] == Integer.MAX_VALUE ? "∞" : dist[i]));
        }
    }
}
